#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    bool vis[7][7];
    int m, n;
    bool exist(vector<vector<char>>& board, string word) {
        m = board.size(), n = board[0].size();
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (board[i][j] == word[0])
                {
                    vis[i][j] = true;
                    if (dfs(board, i, j, word, 1)) return true;
                    vis[i][j] = false;
                }
            }
        }
        return false;
    }
    bool dfs(vector<vector<char>>& board, int i, int j, string& word, int pos)
    {
        if (pos == word.size()) return true;
        int kx[4] = { 0,0,1,-1 };
        int ky[4] = { -1,1,0,0 };
        for (int k = 0; k < 4; k++)
        {
            int dx = kx[k] + i, dy = ky[k] + j;
            if (dx >= 0 && dx < m && dy >= 0 && dy < n && !vis[dx][dy] && board[dx][dy] == word[pos])
            {
                vis[dx][dy] = true;
                if (dfs(board, dx, dy, word, pos + 1)) return true;
                vis[dx][dy] = false;

            }
        }
        return false;
    }
};